package day03;

// 练习2：
// 全排列 【回溯算法/试错】
// 不会写版本

import java.util.ArrayList;
import java.util.List;

public class Main1 {
    // 回溯算法计算全排列
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;  // 数组长度，也就是深度，一会儿用于判断递归结束
        // 使用一个动态数组/链表保存所有的全排列结果
        List<List<Integer>> ret = new ArrayList<>();

        // 判断长度
        if(len == 0) {
            return ret;
        }

        // 此时就要进行全排列
        // 进行初始状态的设定
        boolean[] used = new boolean[len];
        // 每一个排列
        List<Integer> path = new ArrayList<>();

        // 沈度从0开始，相等则结束
        dfs(nums,len,0,path,used,ret);
        return ret;
    }

    // 全排列函数
    private static void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used,
                            List<List<Integer>> ret) {
        // 如果长度==深度，说明一次排列结束
        if(len == depth) {
            // 注意path所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表
            // 所以要再拷贝一份
            ret.add(new ArrayList<>(path));
            return;
        }

        // 在非叶子结点处，产生不同的分支，这一操作的语义是：
        // 在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
        for (int i = depth; i < len; i++) {
            if(!used[i]) { // 说明此时还没有被使用过，作为固定首元素，选择下一个全排列
                // 将该元素作为头加入到一个排列path中，并修改状态为已经使用过
                path.add(nums[i]);
                used[i] = true;
            }
            // 开始下一个全排列
            dfs(nums, len, depth + 1, path, used, ret);
            // 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
            used[i] = false;
            path.remove(path.size()-1); // 参数表示下标
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        Main1 main1 = new Main1();
        List<List<Integer>> lists = main1.permute(nums);
        System.out.println(lists);
    }
}
